Cae Sabah (trước đây gọi là Bắc Borneo thuộc Anh) và Sarawak đều là những thuộc địa riêng biệt của Anh và không thuộc về thuộc địa Mã Lai, và cũng đã không trở thành một phần của Liên bang Mã Lai vào năm 1957. Tuy nhiên, sau đó cả hai đều đã gia nhập Liên bang Malaysia vào năm 1963, khi Singapore cũng gia nhập vào liên bang này, tuy nhiên chính Singapore đã bị khai trừ khỏi Liên bang năm 1965. Trước đó, có những cố gắng để thống nhất Brunei, Sabah và Sarawak thành một Liên bang Bắc Borneo nhưng đã không có kết quả do xuất hiện cuộc nổi loạn ở Brunei.

Có những tranh luận về việc Sabah và Sarawak gia nhập vào Liên bang Malaysia với vị thế ngang hàng với Liên bang Mã lai và Singapore hay với vị thế đơn thuần giống như các bang của Mã Lai.[10] Sự nhất trí được đưa ra là dường như Sabah và Sarawak chỉ là một trong các bang trong liên bang với một mức độ tự trị cao hơn không đáng kể khi so sánh với các bang khác tại Malaysia bán đảo. Ví dụ, cả hai bang đều có quyền kiểm soát việc nhập cư một cách riêng biệt, đòi hỏi các công dân Malaysia đến từ vùng lãnh thổ phía tây phải mang hộ chiếu hay thẻ căn cước khi họ đến Đông Malaysia. Trong khi các bang ở bán đảo phía Tây không có một hạn chế nào về việc đi lại giữa các bang.

Hòn đảo Labuan gia nhập Malaysia và trở thành một phần của Sabah vào năm 1963, sau đó đảo trở thành một Lãnh thổ Liên bang vào năm 1984. Đảo này được sử dụng để thành lập một trung tâm tài chính ngoài khơi từ năm 1990[11]